package Algorithm;

public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
        public TreeNode root;
        public TreeNode searchNode(int key){
            TreeNode cur=root;
            while(cur!=null){
                if(cur.val==key){
                    return cur;
                }else if(cur.val<key){
                    cur=cur.right;
                }else{
                    cur=cur.left;
                }
            }
            return null;
        }
        //插入
        public void insert(int key){
            TreeNode node=new TreeNode(key);
            if(root==null){
                root=new TreeNode(key);
            }
            TreeNode cur=root;
            TreeNode pre=null;
            while (cur!=null){
                if(cur.val<key){
                    pre=cur;
                    cur=cur.right;
                }else if(cur.val>key){
                    pre=cur;
                    cur=cur.left;
                }else{
                    return;
                }
            }
            if(pre.val<key){
                pre.right=node;
            }else{
                pre.left=node;
            }
            System.out.println("插入成功");
        }
        //删除
        public void remove(int key){
            TreeNode cur=root;
            TreeNode pre=null;
            while(cur!=null){
                if(cur.val<key){
                    pre=cur;
                    cur=cur.right;
                }else if(cur.val>key){
                    pre=cur;
                    cur=cur.left;
                }else{
                    //找到了，开始进行删除
                    removeNode(cur,pre);
                }
            }
        }

        private void removeNode(TreeNode cur, TreeNode pre) {
            if(cur.left==null){
                if(cur==root){
                    root=root.right;
                }else if(cur==pre.left){
                    pre.left=cur.right;
                }else{
                    pre.right=cur.right;
                }
            }else if(cur.right==null){
                if(cur==root){
                    root=root.left;
                }else if(cur==pre.left){
                    pre.left=cur.left;
                }else{
                    pre.right=cur.right;
                }
            }else{

            }
        }
    }
}
